package com.huangkailong.leetcode;

/**
 * 实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。<br/>
 * <br/>
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。<br/>
 * <br/>
 * 必须 原地 修改，只允许使用额外常数空间。<br/>
 * <br/>
 * <br/>
 * <br/>
 * 示例 1：<br/>
 * <br/>
 * 输入：nums = [1,2,3]<br/>
 * 输出：[1,3,2]<br/>
 * 示例 2：<br/>
 * <br/>
 * 输入：nums = [3,2,1]<br/>
 * 输出：[1,2,3]<br/>
 * 示例 3：<br/>
 * <br/>
 * 输入：nums = [1,1,5]<br/>
 * 输出：[1,5,1]<br/>
 * 示例 4：<br/>
 * <br/>
 * 输入：nums = [1]<br/>
 * 输出：[1]<br/>
 * <br/>
 * <br/>
 * 提示：<br/>
 * <br/>
 * 1 <= nums.length <= 100<br/>
 * 0 <= nums[i] <= 100<br/>
 * <br/>
 * @author huangkl
 * @date 2021-06-23 12:06
 */
public class NextPermutation {
    /**
     *
     */
    public static void solution1(int[] nums){
        if(nums.length <= 1){
            return;
        }

        int i = nums.length - 1;
        boolean hasNext = false;
        while (i > 0){
            if(nums[i-1] < nums[i]){
                i = i-1;
                hasNext = true;
                break;
            }
            i--;
        }

        int start = hasNext ? i+1 : 0;
        int end = nums.length-1;
        if(hasNext){
            // 交换
            for (int j = nums.length - 1; j >= 0; j--) {
                if(nums[j] > nums[i]){
                    swap(nums, i, j);
                    break;
                }
            }
        }

        // 排序
        reverse(nums, start, end);
    }

    public static void swap(int[] nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    public static void reverse(int[] nums, int i, int j){
        int len = j - i + 1;
        int mid = i+len / 2;
        int l, r;
        if(len%2 == 0){
            l = mid-1;
            r = mid;
        }else{
            l = mid-1;
            r = mid+1;
        }
        while (l >= i){
            swap(nums, l--, r++);
        }
    }
}
